from typing import List


class Solution:
    """
    面试经典150题-[数组/字符串]-80. 删除有序数组中的重复项 II
    给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

    不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
    """

    def removeDuplicates(self, nums: List[int]) -> int:
        """
        :param nums:
        :return:
        解题思路：注意是有序数据组，这很重要！！！注意！！！
        用当前指针指的值、往前数第二个值，对比，判断是不是重复
        左指针一直指着有效数据的后一位，右指针去控制判断是否是有效数据
        """
        left = 2
        right = 2
        while right < len(nums):
            if nums[right] != nums[left - 2]:
                nums[left] = nums[right]
                left += 1
                right += 1
            else:
                right += 1
        return left - 1

    def removeDuplicates_for(self, nums: List[int]) -> int:
        """
        :param nums:
        :return:
        解题思路：注意是有序数据组，这很重要！！！注意！！！
        用当前指针指的值、往前数第二个值，对比，判断是不是重复
        """
        left = 2
        list_i = list(range(nums.__len__()))
        for right in list_i[2:]:
            if nums[right] != nums[left - 2]:
                nums[left] = nums[right]
                left += 1
                right += 1
            else:
                right += 1
        return left

    def removeDuplicates_review_20250729(self, nums: List[int]) -> int:
        """
        解题思路：
        ！！！注意是有序数组
        左指针，从下标1开始，遍历，只要满足（和前面相等但是和后面不相等的）或者（和前面不相等的），就是有效值，+1
        """
        left = 1
        right = 2
        while right < len(nums):
            if (nums[left] == nums[left - 1] and nums[left] != nums[right]) or nums[left] != nums[left - 1]:
                left += 1
                nums[left] = nums[right]
            right += 1
        return left + 1

    def removeDuplicates_review_20250802(self, nums: List[int]) -> int:
        """
        解题思路：左右指针，左指针控制检测过的有效值，右指针遍历
        """
        left = 1
        right = 2
        while right < len(nums):
            if (nums[left] == nums[left - 1] and nums[left] != nums[right]) or nums[left] != nums[left - 1]:
                left += 1
                nums[left] = nums[right]  # 漏了，更新有效值索引后（left加1了），要记得记录有效值
            # else:
            #     nums[right] = nums[right + 1]
            right += 1
        return left + 1


if __name__ == '__main__':
    s = Solution()
    # nums = [1, 1, 1, 2, 2, 3]
    nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
    # nums_len = s.removeDuplicates(nums)
    # nums_len = s.removeDuplicates_for(nums)
    # nums_len = s.removeDuplicates_review_20250729(nums)
    nums_len = s.removeDuplicates_review_20250802(nums)
    print(nums_len, nums[:nums_len])
